Relational databases store information in indexed tables. A user retrieves information from the tables by entering input that is converted to queries by a database application. The database application submits the queries to a database server. In response to a query, the database server accesses the tables specified in the query to determine which information within the tables satisfies the queries. The information that satisfies the queries is then retrieved by the database server and transmitted to the database application and ultimately to the user.
For any given database application, the queries must conform to the rules of a particular query language. Most query languages provide users with a variety of ways to specify information to be retrieved. For example, in the Structured Query Language (SQL), the following query requests the retrieval of the information contained in all rows of table t1:
SELECT * FROM t1
Table t1 (100) is shown in FIG. 1. Table 100 comprises three user columns, 120-124, and eighteen rows (130-164). Table 100 also has an internal column, or pseudocolumn, referred to as rowid. A table's rowid pseudocolumn is not displayed when the structure of the table is list. However the rowid is retrievable by query and uniquely identifies a row in the table. Rowid pseudocolumn 110 has rowid entries that correspond to rows 130-164. Thus, a rowid of eight for table 100 specifies row 144 and no other row of table 100. Columns 120-124 each store numbers, and each column has a name. The name of column 120 is c1, and the names of columns 122 and 124 are c2 and c3, respectively.
The user may constrain the query to retrieve a smaller amount of information by adding a WHERE clause, as in the following query:
SELECT * FROM t1
WHERE c1=2 AND c2&gt;5 AND c3=8
The WHERE clause imposes a constraint that each row of table t1 must meet to satisfy the query. In this case, the WHERE clause has three predicates, c1=2, c2&gt;5, and c3=8. These predicates mean that all the retrieved rows of table t1 must have a value equal to two in column c1, a value greater than five in column c2, and a value equal to eight in column c3, respectively. For table 100, the query would retrieve only row 144.
Without special processing, a database server would have to fetch every row of a table and inspect every column named in the WHERE clause to perform the query. However, such an approach impairs the overall database system performance because many disk blocks would have to be read. As a result, many database systems provide indexes to increase the speed of the data retrieval process. A database index is similar to a normal index found at the end of a book, in that both kinds of indexes comprise an ordered list of information accompanied with the location of the information. Values in one or more columns are stored in an index, maintained separately from the actual database table.
In FIG. 2(a), index 200 is an index built on column c1 of table 100. Each entry, 230-244, in index 200 has a key value 210 and at least one rowid 220. Since the key values are ordered, it can quickly be determined, for example, that the rows that have a key value of "2" in column c1 are those rows associated with rowids 3, 7, 8, 13, and 14 (see index entry 232). An index may be implemented in a variety of ways well known in the art, such as with B-trees, depending on the specific performance characteristics desired for the database system.
FIG. 2(b) shows a B-tree implementation of index 200. A B-tree consists of a set of nodes connected in a hierarchical arrangement. A B-tree contains two types of nodes: branch nodes and leaf nodes. Leaf nodes reside at the lowest level of the hierarchy and contain values from the actual column to which the index corresponds. For example, B-tree 200 is an index for column 120 of table 100 and has leaf nodes 272, 274, and 276. Node 272 is a leaf node that contains a value from column 120. Along with the values, leaf nodes store the rowid of the rows that contain the values. For example, in addition to the number 4, leaf node 272 contains the rowid 6 which corresponds to the row 140 of table 100 that contains the number 4 in column 120. In other words, leaf node 272 contains index entry 236, and a leaf node may contain more than one index entry.
All the nodes in B-tree 200 that are not leaf nodes are branch nodes. Branch nodes contain information that indicates a range of values. In the illustrated B-tree 200, nodes 250, 260, 262, and 264 are branch nodes and therefore correspond to a range of values. The range of values identified in each branch node is such that all nodes that reside below a given branch node correspond to values that fall within the range of values represented by the branch node. For example, node 262 is a branch node that corresponds to numbers in the numerical range from four to six. Consequently, nodes 272, 274, and 276 which all reside below node 262 in the hierarchy, correspond to values that fall within the range from four to six. Reference numbers 270 and 278 represent connections to other portions of B-tree 200 that are not shown.
A database server can use index 200 to process the exemplary query listed above because index 200 is built on a column referenced in one of the predicates of the WHERE clause. Specifically, the WHERE clause contains the predicate c1=2, and index 200 is built on column c1.
A combination of (1) an index and (2) a predicate containing a column upon which the index is built constitutes an "index access method." For example, the WHERE clause described above includes the predicate c1=2. Thus, the database server can use an index access method which specifies that index 200 is accessed to retrieve the rowids of the rows in table 100 where c1=2. Once the rowids are retrieved from index 200, the corresponding rows are retrieved from the table 100. In using index 200 with the predicate c1=2 as an index access method, only five rows instead of eighteen rows would have to be fetched from table 100, reducing the amount of overhead required to process the query.
For a given table, there may be several indexes available for use during a data retrieval. For example, table 100 may have an index based on column 120 (index 200), another index based on column 122 (index 300 of FIG. 3), and an index based on column 124 (index 400 of FIG. 4). Moreover, index 500 of FIG. 5 is a multi-column index built on two columns 124 and 120, in that order, of table 100. The key value of a multi-column index is a concatenation of column values from the index upon which the multi-column index was built. For example, the key value for row 558 lists a value 8 taken from column 124 of table 100 followed by a value of 2 taken from column 120 of table 100.
An index access path is a combination of index access methods used by a database server in retrieving data from a table. Conventionally, database servers generate index access paths on an ad-hoc, first-come, first-served basis. Thus, a database server may always use an index on a column specified in the first predicate of a WHERE clause, even though other indexes may be available for the columns specified in subsequent predicates of the WHERE clause.
A drawback to the conventional approach of generating an index access path is that the performance characteristics for a data retrieval may vary greatly depending on the choice of an index access path. In the example given above, accessing table 100 based on index 200 for the WHERE clause yields a rowid list of five rowids (index entry 232). Accessing table 100 based on index 300, however, yields a rowid list of eight entries (see index entries 340-346). Moreover, accessing table 100 based on index 400 yields a three-entry rowid list (index entry 446). Finally, using index 500 to access table 100 yields a two-entry rowid list (entry 558). Thus, an index access path using multi-column index 500 fetches the least number of rows from table 100. Of the single column indexes, index 400 reduces the amount of processing the most, requiring only three row fetches. However, the first-come, first-served approach will not select either index 400 or 500 if the predicate referring to the columns indexed by either index is not first in the WHERE clause. Therefore, it is desirable to provide a way in which particular indexes with superior performance characteristics are selected for an index access path.
In another conventional approach, a database server may generate for a query an index access path that makes use of more than one index. In the example given above, if a database server uses both indexes 200 and 400 to process the exemplary query, using index 200 for the c1=2 predicate generates a rowid list of 3, 7, 8, 13, and 14. Using index 400 for the c3=8 predicate generates a rowid list of 8, 13, 17, and 18. After the rowid lists have been generated, the database server finds the intersection of the two lists to determine the rows that satisfy both conditions. In this case, these rows are identified by the rowids of 8 and 13. Therefore, a database server using a plurality of indexes to generate and intersect a plurality of rowid lists can reduce the processing involved in handling a query. In this case, only two rows from table 100 (i.e. rows 144 and 154) need to be fetched.
However, generating lists of rowids and intersecting the lists also consumes processing resources, and it is possible to overselect the number of indexes to use. For example, using index 200 generates a rowid list of 3, 7, 8, 13, and 4 and using index 400 yields a rowid list of 8, 13, and 17. The intersection of these two rowid lists is a list of the rowids in common or 8 and 13. If an index access method for index 300 is also selected, then another rowid list of eight entries--2, 5, 8, 9, 12, 15, 16, and 18 --would be generated and intersected with the rowid lists from indexes 200 and 400. The result would be a rowid list of rowid 8. Even though using index 300 has a marginal benefit of reducing by one the number of rows that would have to be fetched from table 100, the cost of generating that eight-entry rowid list and finding another intersection can exceed that marginal benefit. Therefore, it is desirable to generate an index access path without overselecting the indexes in processing a query.
One advantage of both conventional approaches is that there is relatively little overhead associated with the index selection process. In contrast, an exhaustive search of all the possible index access paths for a query requires a substantial amount of computing resources. In fact, it is possible that an exhaustive search consumes more computing resources than the savings it produces in finding the best performing index access path.
Therefore, it is desirable to generate a better performing index access path without having to inspect every possible selection of indexes.